// 线段树：区间信息合并
// 给出长度为N的序列和Q个询问，每次询问一段区间内最大值与最小值的差。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 50005;

int n, q;
int a[N];
int f[N<<2], g[N<<2];

void build(int x, int l, int r) // 初始化线段树
{
	if(l==r)
	{
		f[x] = g[x] = a[l];
		return;
	}
	
	int mid = (l+r)>>1;
	build(x+x, l, mid); // 分成两个子区间
	build(x+x+1, mid+1, r); // 分成两个子区间
	f[x] = min(f[x+x], f[x+x+1]); // 区间信息合并
	g[x] = max(g[x+x], g[x+x+1]); // 区间信息合并
}

int ansmi, ansma;
int opl, opr;

void query(int x, int l, int r)
{
	if(opl <= l && r <= opr) // 当前区间在目标区间内
	{
		ansmi = min(ansmi, f[x]); // 更新答案
		ansma = max(ansma, g[x]);
		return;
	}
	
	int mid = (l+r) >> 1;
	if(opl <= mid) query(x+x, l, mid); // 若左区间可能出现在目标区间内，则递归处理
	if(opr > mid) query(x+x+1, mid+1, r); // 若右区间可能出现在目标区间内，则递归处理
}

void update(int x, int l, int r) // 修改某一位置上的值
{
	if(opl <= l && r <= opr)
	{
		f[x] = opx; // 更新值
		return;
	}
	
	int mid = (l+r) >> 1;
	if(opl <= mid) update(x+x, l, mid);
	if(opr > mid) update(x+x+1, mid+1, r);
	f[x] = min(f[x+x], f[x+x+1]); // 在递归处理左右子区间后，记得要更新此区间的值
}

int main()
{
	freopen("seg1.in", "r", stdin);
	freopen("seg1.out", "w", stdout);
	
	scanf("%d%d", &n, &q);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	
	build(1, 1, n);
	
	for(int i=1, l, r; i<=q; i++)
	{
		scanf("%d%d", &l, &r);
		opl = l, opr = r;
		ansmi = 2e9, ansma = 0;
		query(1, 1, n);
		printf("%d\n", ansma - ansmi);
	}
	
	return 0;
}
